#define _CRT_SECURE_NO_WARNINGS

//最小的k个数 -- 基于数组划分思想利用快速选择算法实现

class Solution {
public:
    int random(vector<int>& arr, int l, int r)
    {
        return arr[rand()%(r-l)+r];
    }
    void qsort(vector<int>& arr, int l, int r, int k)
    {
        if(l >= r)
        {
            return;
        }
        int key = random(arr, l, r);
        int i = l, left = l - 1, right = r + 1;
        while(i < right)
        {
            if(arr[i] < key) swap(arr[i++], arr[++left]);
            else if(arr[i] == key) i++;
            else swap(arr[i], arr[--right]);
        }
        //[l, left] [left + 1, right -1] [right, r]
        // a              b                   c
        //若left-l+1 > k , 则需要去划分后的左区间寻找
        if(left-l+1 > k) return qsort(arr, l, left, k);
        //若right - l >=k, 则已经找到
        else if(right - l >= k) return;
        else return qsort(arr, right, r, k - (left-l+1));
    }
    vector<int> smallestK(vector<int>& arr, int k) {
        srand(time(NULL));
        qsort(arr, 0, arr.size()-1, k);
        return {arr.begin(), arr.begin() + k};
    }
};